package momo.multitree.util;

import momo.multitree.structure.*;

public class EdgeQuickSort
{
	public static void quickSort(Edge array[])
	{
		quickSort(array, 0, array.length - 1);
	}

	private static void quickSort(Edge array[], int start, int end)
	{
		int i = start;
		int k = end;
		if (end - start >= 1)
		{
//			int pivot = array[start].getId();
			String pivot = array[start].getId();

			while (k > i)
			{
//				while (array[i].getId() <= pivot && i <= end && k > i)
				while (array[i].getId().compareTo(pivot) <= 0 && i <= end && k > i)
					i++;

//				while (array[k].getId() > pivot && k >= start && k >= i)
				while (array[k].getId().compareTo(pivot) > 0 && k >= start && k >= i)
					k--;

				if (k > i)
					swap(array, i, k);
			}
			swap(array, start, k);
			quickSort(array, start, k - 1);
			quickSort(array, k + 1, end);
		}else
			return;
	}

	private static void swap(Edge array[], int index1, int index2) 
	{
		Edge temp = array[index1];
		array[index1] = array[index2];
		array[index2] = temp;
	}
	
	public static void main(String args[])
	{
		Node n1 = new Node("1", 1, 1);
		Node n2 = new Node("2", 1, 1);
		Node n3 = new Node("3", 1, 1);
		Node n4 = new Node("4", 1, 1);
		Node n5 = new Node("5", 1, 1);
		Node n6 = new Node("6", 1, 1);
		
		Edge e1 = new Edge("1", n1, n2, 1, 1, 1, 1);
		Edge e2 = new Edge("2", n2, n3, 1, 1, 1, 1);
		Edge e3 = new Edge("3", n3, n4, 1, 1, 1, 1);
		Edge e4 = new Edge("4", n4, n5, 1, 1, 1, 1);
		Edge e5 = new Edge("5", n5, n6, 1, 1, 1, 1);
		
		Graph g = new Graph();
		g.add(e4);
		g.add(e2);
		g.add(e3);
		g.add(e1);
		g.add(e5);
		
		
		Edge[] edges = g.getEdges().toArray(new Edge[0]);
		EdgeQuickSort.quickSort(edges);
		
		for(Edge e: edges)
		{
			System.out.println(e.getId());
		}
	}
}